Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints

摘要

We consider a service system model primarily motivated by the problem ofefficient assignment of virtual machines to physical host machines in a networkcloud, so that the number of occupied hosts is minimized. There are multiple types of arriving customers, where a customer's meanservice time depends on its type. There is an infinite number of servers.Multiple customers can be placed for service into one server, subject togeneral "packing" constraints. Service times of different customers areindependent, even if served simultaneously by the same server. Each newarriving customer is placed for service immediately, either into a serveralready serving other customers (as long as packing constraints are notviolated) or into an idle server. After a service completion, each customerleaves its server and the system. We propose an extremely simple and easily implementable customer placementalgorithm, called Greedy-Random (GRAND). It places each arriving customeruniformly at random into either one of the already occupied servers (subject topacking constraints) or one of the so-called zero-servers, which are emptyservers designated to be available to new arrivals. One instance of GRAND,called GRAND($aZ$), where $a\ge 0$ is a parameter, is such that the number ofzero-servers at any given time $t$ is $aZ(t)$, where $Z(t)$ is the currenttotal number of customers in the system. We prove that GRAND($aZ$) with $a>0$is asymptotically optimal, as the customer arrival rates grow to infinity and$a\to 0$, in the sense of minimizing the total number of occupied servers insteady state. In addition, we study by simulations various versions of GRANDand observe the dependence of convergence speed and steady-state performance onthe number of zero-servers.